package PenTest.Soluation14;

import java.util.*;


   class TreeNode {
    int val = 0;
    TreeNode left = null;
   TreeNode right = null;
    public TreeNode(int val) {
      this.val = val;
    }
  }


/**
 * 题目： 判断是否平衡二叉树
 *
 * 解决方法： 深搜+ 剪枝
  */

public class Solution {

    public boolean IsBalanced_Solution (TreeNode pRoot) {
    //    输出
       if(pRoot==null) {
        return true;
       }

        // 一旦找到不符合就返回 false
        if(Math.abs(  isThreeCount(pRoot.left) - isThreeCount(pRoot.right)) > 1) {
            return false;
        } 

        // 左子树不符合就开始剪枝
        if(!IsBalanced_Solution(pRoot.left)) {
            return false;
        }


        // 右子树不符合也剪枝
        if(!IsBalanced_Solution(pRoot.right)) {
            return false;
        }

        // 如果没有就返回 true
       return true;
    }

    private  int isThreeCount(TreeNode root) {
            if(root == null) {
                return 0;
            }

            int left = isThreeCount(root.left);

            int right = isThreeCount(root.right);


            return Math.max(right,left) + 1;

    }
}